package algorithm.simulated_annealing;

import java.awt.Point;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import library.Tracer;

public class SimulatedAnnealing {
	private static final double ALPHA = 0.999;
	private static final double TEMPERATURE = 100.33;
	private static final int MAX_ITERATION = 5;
	public Solution solution;

	public SimulatedAnnealing() {
		solution = new Solution();
	}

	public void find() {
		if (solution.cities.size() <= 1)
			return;
		double temperature = TEMPERATURE, delta_e;

		while (temperature > 0.0001) {
			// Copy the current solution to a temp
			Solution temSol = solution.deepCopy();
			// Monte Carlo iterations
			for (int i = 0; i < MAX_ITERATION; i++) {
				temSol.perturb_tour();
				temSol.compute_tour();
				delta_e = temSol.getTourlength() - solution.getTourlength();

				if (Tracer.isPrinting("scaffolding")) {
					System.out.println("delat" + delta_e);
				}
				// is the new solution better than the old?
				if (delta_e < 0.0) {
					// Accept the new, better, solution
					solution = temSol;
				} else {
					// Probabilistically accept a worse solution
					if (Math.exp(-1 * delta_e / temperature) > temSol.ran.nextDouble()) {
						solution = temSol;
					}
				}
			}
			// Decrease the temperature
			temperature *= ALPHA;
		}
	}
}

class Solution implements Serializable {
	private static final long serialVersionUID = -7143936408563952279L;

	public Solution deepCopy() {
		// oos -> bos, bos->bis, ois -> bis
		try {
			ByteArrayOutputStream bos = new ByteArrayOutputStream();
			ObjectOutputStream oos = new ObjectOutputStream(bos);
			oos.writeObject(this);

			ByteArrayInputStream bis = new ByteArrayInputStream(bos.toByteArray());
			ObjectInputStream ois = new ObjectInputStream(bis);
			return (Solution) ois.readObject();
		} catch (IOException e) {
			e.printStackTrace();
		} catch (ClassNotFoundException e) {
			e.printStackTrace();
		}
		return null;
	}

	public void perturb_tour() {
		int p1, p2;
		City c1, c2;
		do {
			p1 = Math.abs(ran.nextInt()) % cities.size();
			p2 = Math.abs(ran.nextInt()) % cities.size();
		} while (p1 == p2);
		c1 = cities.get(p1);
		c2 = cities.get(p2);

		cities.set(p1, c2);
		cities.set(p2, c1);
	}

	public void compute_tour() {
		tour_length = 0;
		for (int i = 0; i < cities.size() - 1; i++)
			tour_length += euclidean_distance(i, i + 1);
		tour_length += euclidean_distance(cities.size() - 1, 0);
	}

	public double getTourlength() {
		return tour_length;
	}

	private double euclidean_distance(int i, int j) {
		City c1 = cities.get(i);
		City c2 = cities.get(j);
		return Math.sqrt(Math.pow(c1.x - c2.x, 2) + Math.pow(c1.y - c2.y, 2));
	}

	public List<City> cities;
	private double tour_length;
	public Random ran;

	public Solution() {
		cities = new ArrayList<City>();
		tour_length = 0;
		ran = new Random();
	}

	public void disp() {
		for (City c : cities) {
			Tracer.debug("X=%d, Y=%d, name=%s", c.x, c.y, c.name);
		}
		Tracer.debug("Tourlength = %f", getTourlength());
	}
}

class City extends Point implements Serializable {
	public String name;

	public City(int x, int y) {
		name = "city" + (++count);
		this.x = x;
		this.y = y;
	}

	private static int count = 0;
	private static final long serialVersionUID = -8297780440884847104L;
}

//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//